详解C++STL容器系列（一）

您所在的位置：网站首页 › at last的用法总结 › 详解C++STL容器系列（一）

详解C++STL容器系列（一）

#详解C++STL容器系列（一）| 来源: 网络整理| 查看: 265

目录一、介绍二、vector的创建和方法创建vector方法三、vector的具体用法3.1 遍历vector3.1.1 迭代器访问3.1.2 下标访问3.1.3 范围for循环 3.2 vector 容量和大小3.3 vector 常用算法3.3.1 push_back、pop_back 和 emplace_back3.3.2 insert 和 emplace3.3.3 erase3.3.4 assign3.3.5 swap 和 clear 3.4 vector二维操作定义访问resize操作四、vector扩容原理push_back 总结

本文将详细介绍STL容器之vector的用法，并对相关底层原理说明。

一、介绍 vector是STL容器中的一种常用的容器，和数组类似，由于其大小(size)可变，常用于数组大小不可知的情况下来替代数组。vector是为了实现动态数组而产生的容器，然而向量这个名字是STL编写者取名没区好，因为在数学上的向量在几何中是矢量，两者名字相同而意义大相径庭。vector也是一种顺序容器，在内存中连续排列，因此可以通过下标快速访问，时间复杂度为O(1)。然而，连续排列也意味着大小固定，数据超过vector的预定值时vector将自动扩容。二、vector的创建和方法

首先，使用vector时需包含头文件：

#include 创建vector

vector本质是类模板，可以存储任何类型的数据。数组在声明前需要加上数据类型，而vector则通过模板参量设定类型。

比如，声明一个int型的vector数组。

vector arr1; //一个空数组 vector arr2 {1, 2, 3, 4, 5}; //包含1、2、3、4、5五个变量 vector arr3(4); //开辟4个空间，值默认为0 vector arr4(5, 3); //5个值为3的数组 vector arr5(arr4); //将arr4的所有值复制进去，和arr4一样 vector arr6(arr4.begin(), arr4.end()); //将arr4的值从头开始到尾复制 vector arr7(arr4.rbegin(), arr4.rend()); //将arr4的值从尾到头复制方法

iterators（迭代器）

名字描述begin返回指向容器中第一个元素的迭代器。end返回指向容器最后一个元素所在位置后一个位置的迭代器rbegin返回容器逆序的第一个元素的迭代器rend返回容器逆序的最后一个元素的前一个位置的迭代器cbegin和begin()功能相同，在其基础上增加了 const 属性，不能用于修改元素。cend和end()功能相同，在其基础上增加了 const 属性，不能用于修改元素。crbegin和rbegin()功能相同，在其基础上增加了 const 属性，不能用于修改元素。crend和rend()功能相同，在其基础上增加了 const 属性，不能用于修改元素。

Capacity（容量）

名字描述size返回实际元素的个数capacity返回总共可以容纳的元素个数max_size返回元素个数的最大值。这个值非常大，一般是2^32-1empty判断vector是否为空，为空返回true否则falseresize改变实际元素的个数，对应于sizereserve增加容器的容量，控制vector的预留空间shrink_to_fit减少capacity到size的大小，即减小到size的大小

Element access（元素访问）

名字描述operator[]vector可以和数组一样用[]访问元素atvector.at(i)等同于vector[i]，访问数组下表的元素front返回第一个元素back返回最后一个元素data返回指向容器中第一个元素的指针

Modifiers（修改器）

名字描述push_back在容器的尾部插入元素pop_back删除最后一个元素insert插入元素erase删除元素clear清除容器内容，size=0，存储空间不变swap交换两个元素的所有内容assign用新元素替换原有内容。emplace插入元素，和insert实现原理不同，速度更快emplace_back在容器的尾部插入元素，和push_back不同三、vector的具体用法

下面将讲解vector的具体用法

3.1 遍历vector 3.1.1 迭代器访问通过迭代器访问从begin()到end()，需要定义iterator，当然可以用auto替代。begin()表示第一个元素，而end()不是最后一个元素，end()是最后一个元素的前一个位置。 //迭代器：vector::iterator for (vector::iterator it = arr.begin(); it != arr.end(); it++) { cout cout arr.push_back(i); } for (int i = 0; i 1, 2, 3, 4, 5 }; arr.insert(arr.begin(), arrs.begin(), arrs.end());

emplace和insert同为插入元素，不过emplace只能插入一个元素：

//在arr的头部插入值为10的元素 vector arr; arr.emplace(arr.begin(), 10);

insert和emplace的区别和上面类似，就是一个是拷贝和复制的过程，而另一个则是直接创建一个新元素。

3.3.3 erase

erase通过迭代器删除某个或某个范围的元素，并返回下一个元素的迭代器。

vector arr{1, 2, 3, 4, 5}; //删除arr开头往后偏移两个位置的元素，即arr的第三个元素，3 arr.erase(arr.begin() + 2); //删除arr.begin()到arr.begin()+2之间的元素，删除两个;即删除arr.begin()而不到arr.begin()+2的元素 arr.erase(arr.begin(), arr.begin() + 2); 3.3.4 assign

assign修改vector，和insert操作类似，不过insert是从尾部插入，而assign则将整个vector改变。

将整个vector修改为n个值为val的容器

//将arr修改为3个值为5的vector。 vector arr = {5, 4, 3, 2, 1}; arr.assign(3, 10);

将整个vector修改为某个容器[start, end]范围内的元素

//将arr修改为范围[arrs.begin, arrs.end]内的元素 vector arr = {5, 4, 3, 2, 1}; vector arrs = { 1, 2, 3, 4, 5 }; arr.assign(arrs.begin(), arrs.end());

用数组的值进行范围修改

//将arr替换为数组arrs vector arr = {5, 4, 3, 2, 1}; int arrs[5] = { 1, 2, 3, 4, 5 }; arr.assign(arrs, arrs + 5); 3.3.5 swap 和 clear

swap将两个vector进行交换。

vector arr = {5, 4, 3, 2, 1}; vector arrs = { 1, 2, 3, 4, 5 }; arr.swap(arrs);

clear清空整个vector，size变为0，但空间仍然存在。

arr.clear(); 3.4 vector二维操作

实际上，二维vector其实就是嵌套定义vector，那么对其进行操作我们可以从嵌套的vector得到单层的vector，就可以调用其方法了。

定义 vector arr; //定义一个空的二维vector vector arr(5, vector(3, 1)); //定义一个5行3列值全为1的二维vector 访问

和二维数组一样通过 [] [] 访问即可。

for (int i = 0; i cout cout arr.push_back(i); cout return _Max; } //采取1.5倍扩容 const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2; //扩容后仍然小于新加入元素后的大小，以新加入元素后的大小为准 if (_Geometric emplace_back(_Val); } void push_back(_Ty&& _Val) { emplace_back(_STD move(_Val)); }

接着，进入emplace_back函数。判断capacity和size是否相等，如果相等就进入_Emplace_reallocate函数。

tips:对于size和capacity，代码里通过这三个指针实现内存管理。在这里插入图片描述

template decltype(auto) emplace_back(_Valty&&... _Val) { auto& _My_data = _Mypair._Myval2; pointer& _Mylast = _My_data._Mylast; if (_Mylast != _My_data._Myend) { return _Emplace_back_with_unused_capacity(_STD forward(_Val)...); } _Ty& _Result = *_Emplace_reallocate(_Mylast, _STD forward(_Val)...); #if _HAS_CXX17 return _Result; #else // ^^^ _HAS_CXX17 ^^^ // vvv !_HAS_CXX17 vvv (void) _Result; #endif // _HAS_CXX17 }

我们进入_Emplace_reallocate函数。在这函数里，首先会检查size是否等于max_size，超过最大值时触发错误。接着，就看到了之前提到的扩容函数 _Calculate_growth，修改capacity的值。

template pointer _Emplace_reallocate(const pointer _Whereptr, _Valty&&... _Val) { _Alty& _Al = _Getal(); auto& _My_data = _Mypair._Myval2; pointer& _Myfirst = _My_data._Myfirst; pointer& _Mylast = _My_data._Mylast; _STL_INTERNAL_CHECK(_Mylast == _My_data._Myend); const auto _Whereoff = static_cast(_Whereptr - _Myfirst); const auto _Oldsize = static_cast(_Mylast - _Myfirst); if (_Oldsize == max_size()) { _Xlength(); } const size_type _Newsize = _Oldsize + 1; const size_type _Newcapacity = _Calculate_growth(_Newsize); const pointer _Newvec = _Al.allocate(_Newcapacity); const pointer _Constructed_last = _Newvec + _Whereoff + 1; pointer _Constructed_first = _Constructed_last; _TRY_BEGIN _Alty_traits::construct(_Al, _Unfancy(_Newvec + _Whereoff), _STD forward(_Val)...); _Constructed_first = _Newvec + _Whereoff; if (_Whereptr == _Mylast) { // at back, provide strong guarantee _Umove_if_noexcept(_Myfirst, _Mylast, _Newvec); } else { // provide basic guarantee _Umove(_Myfirst, _Whereptr, _Newvec); _Constructed_first = _Newvec; _Umove(_Whereptr, _Mylast, _Newvec + _Whereoff + 1); } _CATCH_ALL _Destroy(_Constructed_first, _Constructed_last); _Al.deallocate(_Newvec, _Newcapacity); _RERAISE; _CATCH_END _Change_array(_Newvec, _Newsize, _Newcapacity); return _Newvec + _Whereoff; } 总结

vector在项目或者刷题中有大量的运用，熟练掌握他们的用法是必不可少的一步。同时，vector扩容的机制就是面试常考的题目，理解其源码对我们编写代码也有很大益处。

【本文地址】

详解C++STL容器系列（一）

详解C++STL容器系列（一）

今日新闻

推荐新闻